/**
 * @program: LeetCode
 * @description: LeetCode : 5. 最长回文子串
 * @author: WXY
 * @create: 2023-03-09 14:05
 * @Version 1.0
 **/
public class Num5_longestPalindrome {
    public static String longestPalindrome(String s) {
        char[] str = s.toCharArray();
        boolean[][] dp = new boolean[str.length][str.length];
        int maxLength = 0;
        int left = 0;
        int right = 0;
        for (int i = str.length - 1; i >= 0 ; i--) {
            for (int j = i; j < str.length; j++) {
                if (str[i] == str[j]) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]){
                        dp[i][j] = true;
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left, right + 1);
    }

    public static void main(String[] args) {
        String s = "abbdddbb";
        String s1 = longestPalindrome(s);
        System.out.println(s1);
    }
}
